package com.longshine.arthmetic.sort;

import com.longshine.arthmetic.Util;

/**
 * 堆排序
 *  
 *
 * @classname   HeapSort.java 
 * @author      YitianC
 * @version     Revision: 1.1,  Date: 2008/05/14 01:43:47  
 * @history     
 *              Apr 6, 2012 3:55:29 PM  
 *
 */
public class HeapSort {

	public static void heapSort(int[] data){
		int l = data.length;
		for(int i=0;i<l;i++){
			buildMaxHeap(data,l-i-1);
			Util.swap(data, 0, l-i-1);
		}
	}
	public static void buildMaxHeap(int[] data,int lastIndex){
		int j = 0;
		int big = 0;
		for(int i=(lastIndex-1)/2;i>=0;i--){
			j = i;
			while(2*j+1<=lastIndex){
				big = 2*j+1;
				if(big+1<=lastIndex){
					if(data[big]<data[big+1]){
						big = big+1;
					}
				}
				if(data[j]<data[big]){
					Util.swap(data, big, j);
					j = big;
				}
				else{
					break;
				}
			}
		}
	}
	
	public static void main(String[] args){
		
		int [] t = new int[]{5,8,1,20,15,13,7,6,30,45,14};
		Util.printArray(t);
		heapSort(t);
		Util.printArray(t);
	}
}
